package com.shm.leetcode;

import java.util.Arrays;

/**
 * 1774. 最接近目标价格的甜点成本
 * 你打算做甜点，现在需要购买配料。目前共有 n 种冰激凌基料和 m 种配料可供选购。而制作甜点需要遵循以下几条规则：
 *
 * 必须选择 一种 冰激凌基料。
 * 可以添加 一种或多种 配料，也可以不添加任何配料。
 * 每种类型的配料 最多两份 。
 * 给你以下三个输入：
 *
 * baseCosts ，一个长度为 n 的整数数组，其中每个 baseCosts[i] 表示第 i 种冰激凌基料的价格。
 * toppingCosts，一个长度为 m 的整数数组，其中每个 toppingCosts[i] 表示 一份 第 i 种冰激凌配料的价格。
 * target ，一个整数，表示你制作甜点的目标价格。
 * 你希望自己做的甜点总成本尽可能接近目标价格 target 。
 *
 * 返回最接近 target 的甜点成本。如果有多种方案，返回 成本相对较低 的一种。
 *
 *
 *
 * 示例 1：
 *
 * 输入：baseCosts = [1,7], toppingCosts = [3,4], target = 10
 * 输出：10
 * 解释：考虑下面的方案组合（所有下标均从 0 开始）：
 * - 选择 1 号基料：成本 7
 * - 选择 1 份 0 号配料：成本 1 x 3 = 3
 * - 选择 0 份 1 号配料：成本 0 x 4 = 0
 * 总成本：7 + 3 + 0 = 10 。
 * 示例 2：
 *
 * 输入：baseCosts = [2,3], toppingCosts = [4,5,100], target = 18
 * 输出：17
 * 解释：考虑下面的方案组合（所有下标均从 0 开始）：
 * - 选择 1 号基料：成本 3
 * - 选择 1 份 0 号配料：成本 1 x 4 = 4
 * - 选择 2 份 1 号配料：成本 2 x 5 = 10
 * - 选择 0 份 2 号配料：成本 0 x 100 = 0
 * 总成本：3 + 4 + 10 + 0 = 17 。不存在总成本为 18 的甜点制作方案。
 * 示例 3：
 *
 * 输入：baseCosts = [3,10], toppingCosts = [2,5], target = 9
 * 输出：8
 * 解释：可以制作总成本为 8 和 10 的甜点。返回 8 ，因为这是成本更低的方案。
 * 示例 4：
 *
 * 输入：baseCosts = [10], toppingCosts = [1], target = 1
 * 输出：10
 * 解释：注意，你可以选择不添加任何配料，但你必须选择一种基料。
 *
 *
 * 提示：
 *
 * n == baseCosts.length
 * m == toppingCosts.length
 * 1 <= n, m <= 10
 * 1 <= baseCosts[i], toppingCosts[i] <= 104
 * 1 <= target <= 104
 *
 */
public class ClosestCost {
    int res;
    /**
     * 方法一：回溯
     * 思路与算法
     *
     * 首先题目给出长度分别为 nn 的冰淇淋基料数组 \textit{baseCosts}baseCosts 和长度为 mm 的配料数组 \textit{toppingCosts}toppingCosts，其中 \textit{baseCosts}[i]baseCosts[i] 表示第 ii 种冰淇淋基料的价格，\textit{toppingCosts}[j]toppingCosts[j] 表示一份第 jj 种冰淇淋配料的价格，以及一个整数 \textit{target}target 表示我们需要制作甜点的目标价格。现在在制作甜品上我们需要遵守以下三条规则：
     *
     * 必须选择一种冰淇淋基料；
     * 可以添加一种或多种配料，也可以不添加任何配料；
     * 每种配料最多两份。
     * 我们希望做的甜点总成本尽可能接近目标价格 \textit{target}target，那么我们现在按照规则对于每一种冰淇淋基料用回溯的方式来针对它进行甜品制作。又因为每一种配料都是正整数，所以在回溯的过程中总开销只能只增不减，当回溯过程中当前开销大于目标价格 \textit{target}target 后，继续往下搜索只能使开销与 \textit{target}target 的差值更大，所以如果此时差值已经大于等于我们已有最优方案的差值，我们可以停止继续往下搜索，及时回溯。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode.cn/problems/closest-dessert-cost/solution/zui-jie-jin-mu-biao-jie-ge-de-tian-dian-2ck06/
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n \times 3^m)O(n×3
     * m
     *  )，其中 nn，mm 分别为数组 \textit{baseCosts}baseCosts，\textit{toppingCosts}toppingCosts 的长度。
     * 空间复杂度：O(m)O(m)，主要为回溯递归的空间开销。
     * 枚举所有能选的基料，选定一种基料后，搜索所有配料的可能性，每种配料有三种选择：[选1个，选2个，不选][选1个，选2个，不选]，保存最优的结果即可。
     * @param baseCosts
     * @param toppingCosts
     * @param target
     * @return
     */
    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        res = Arrays.stream(baseCosts).min().getAsInt();
        for (int cost : baseCosts) {
            dfs(toppingCosts,0,cost,target);
        }
        return res;
    }

    private void dfs(int[] toppingCosts, int i, int cost, int target) {
        if (Math.abs(res-target)<(cost-target)){
            return;
        }else if (Math.abs(res-target)>=Math.abs(cost-target)){
            if (Math.abs(res-target)>Math.abs(cost-target)){
                res=cost;
            }else {
                res = Math.min(res,cost);
            }
        }
        if (i==toppingCosts.length){
            return;
        }
        dfs(toppingCosts,i+1,cost+toppingCosts[i],target);
        dfs(toppingCosts,i+1,cost+toppingCosts[i]*2,target);
        dfs(toppingCosts,i+1,cost,target);
    }
}
